import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 * [7],
 * [2,2,3]
 * ]
 * 示例 2：
 * <p>
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为：
 * [
 *   [2,2,2,2],
 *   [2,3,3],
 *   [3,5]
 * ]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= candidates.length <= 30
 * 1 <= candidates[i] <= 200
 * candidate 中的每个元素都是独一无二的。
 * 1 <= target <= 500
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.combinationSum(new int[]{1, 2}, 4);
        System.out.println(lists.size());
    }


    /**
     * 记录最后结果
     **/
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    /**
     * 记录暂时的结果
     **/
    List<Integer> sequence = new ArrayList<Integer>();

    /**
     * 使用递归
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, 0, target);
        return ans;
    }

    /**
     * 从0开始进入递归，直接递归下去，增加回溯
     *
     * @param pos
     * @param rest
     */
    public void dfs(int[] candidates, int pos, int rest) {
        if (pos == candidates.length) {
            return;
        }
        if (rest == 0) {
            ans.add(new ArrayList<>(sequence));
            return;
        }
        // 如果不消费
        dfs(candidates, pos + 1, rest);
        // 如果消费
        if (rest - candidates[pos] >= 0) {
            sequence.add(candidates[pos]);
            dfs(candidates, pos, rest - candidates[pos]);
            sequence.remove(sequence.size() - 1);
        }
    }

}